package com.zhn;

/**
 * m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：
 *
 * 每行中，每棵植物的右侧相邻植物不矮于该植物；
 * 每列中，每棵植物的下侧相邻植物不矮于该植物。
 *
 * 请判断 plants 中是否存在目标高度值 target
 *
 *
 * 输入：plants = [[2, 3 ,6, 8],
 *                [4 ,5 ,8, 9],
 *                [5, 9,10,12]],
 *        target = 8
 *
 * 输出：true
 */

//利用二维数组的有序特性进行求解
//从二维数组的右上角开始元素的查询，记行索引为i,列索引为j,
//因为每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，所以右上角的元素为第一行的最大值，最后一列的最小值，

public class FindTargetIn2DPlants {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        if(plants.length == 0 || plants == null)
            return false;
        int col = 0;
        int row = plants[0].length-1;
        while(col < plants.length && row >= 0){
            //从右上方开始向左下遍历
            if(plants[col][row] == target){
                return true;
            }else if (plants[col][row] > target) {
                //向左移动
                row--;
                continue;
            }else {
                //向下移动
                col++;
                continue;
            }
        }
        return false;
    }

}
